package com.code.link.doubleLinked;

/**
 * 双向链表
 */
public class DoubleLinkedList {
    private Link first;
    //使其具有双端链表的属性
    private Link last;

    public DoubleLinkedList() {
        first = null;
        last = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    //insert at front of list
    public void insertFirst(long dd) {
        Link newLink = new Link(dd);
        if (isEmpty()) {
            last = newLink;
        } else {
            first.previous = newLink;
        }
        newLink.next = first;
        first = newLink;
    }

    //insert at end of list
    public void insertLast(long dd) {
        Link newLink = new Link(dd);
        if (isEmpty()) {
            first = newLink;
        } else {
            last.next = newLink;
            newLink.previous = last;
        }
        last = newLink;
    }

    //delete first link
    public Link deleteFirst() {
        Link temp = first;
        if (first.next == null) {
            //只有一个结点
            last = null;
        } else {
            first.next.previous = null;
        }
        first = first.next;
        return temp;
    }

    //delete last link
    public Link deleteLast() {
        Link temp = last;
        if (first.next == null) {
            first = null;
        } else {
            //old previous --> null
            last.previous.next = null;
        }
        //last --> old previous
        last = last.previous;
        return temp;
    }

    //insert dd just after key
    public boolean insertAfter(long key, long dd) {
        Link current = first;

        while (current.dData != key) {
            current = current.next;
            if (current == null) {
                //没有找到指定的key
                return false;
            }
        }

        Link newLink = new Link(dd);
        if (current == last) {
            newLink.next = null;
            last = newLink;
        } else {
            newLink.next = current.next;
            current.next.previous = newLink;
        }

        newLink.previous = current;
        current.next = newLink;
        return true;
    }

    public Link deleteKey(long key) {
        Link current = first;
        while (current.dData != key) {
            current = current.next;
            if (current == null) {
                return null;
            }
        }

        if (current == first) {
            first = current.next;
        } else {
            current.previous.next = current.next;
        }

        if (current == last) {
            last = current.previous;
        } else {
            current.next.previous = current.previous;
        }
        return current;
    }

    //从前往后打印
    public void displayForward() {
        System.out.print("List (first-->last): ");
        Link current = first;
        while (current != null) {
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }

    public void displayBackward() {
        System.out.print("List (last-->first): ");
        Link current = last;
        while (current != null) {
            current.displayLink();
            current = current.previous;
        }
        System.out.println("");
    }
}
